// 判断序列是否可能是二叉查找树从根到叶子结点的路径。

// 法一：O(N^2) 对每个位置判断，如果比前一个数大（小），后面都需要比前面的数大（小）
// 法二：O(N) 对每个位置判断，如果比前一个数x大（小），后面的数都要比x更大（小），分别记录后面的数需要大于和小于的数
bool getAns(vector<int>& nums) {
   int larger_rec = INT_MIN;
   int smaller_rec = INT_MAX;
   for (int i = 1; i < nums.size(); ++i) {
       if (nums[i] < larger_rec || nums[i] > smaller_rec)
           return false;
       if (nums[i] > nums[i - 1]) {
           larger_rec = nums[i - 1];
       }
       if (nums[i] < nums[i - 1]) {
           smaller_rec = nums[i - 1];
       }
   }
   return true;
}

int main() {
   vector<int> nums = {1, 5, 9, 8, 7};
   cout << getAns(nums) << endl; 
   return 0;
}